import java.util.Arrays;

public class MyInversePairs {
    int count = 0;
    public static void main(String[] args) {
        MyInversePairs myInversePairs = new MyInversePairs();
        int[] arr = {1,2,10,4,5};
        System.out.println(myInversePairs.InversePairs(arr));
        System.out.println(Arrays.toString(arr));
    }
    public int InversePairs(int [] array) {
        int end = array.length;
        if (end < 2) return 0;
        outTrue(array,0,end-1);
        return count;
    }

    private void outTrue(int[] array, int left, int right) {
        if (right - left < 1){
            return;
        }
        int mid = (left+right)>>>1;
        outTrue(array,left,mid);
        outTrue(array,mid+1,right);
        merge(array,left,mid,right);
    }

    private void merge(int[] array, int left, int mid, int right) {
        int[] arr = new int[right - left + 1];
        int cur = mid + 1;
        int i = 0;
        int l1 = left;
        int r1 = right;

        while (left <= mid && cur <= right){
            if (array[left] <= array[cur]){
                arr[i++] = array[left++];
            }else {
                count = count + mid - left + 1;
                arr[i++] = array[cur++];
            }
        }
        while (left <= mid){
            arr[i++] = array[left++];
        }
        while (cur <= right){
            arr[i++] = array[cur++];
        }
        for (int j = l1; j <= r1; j++) {
            array[j] = arr[j-l1];
        }
    }
}
